A Restless Bandit Model for Resource Allocation, Competition, and Reservation

Abstract

We study a resource allocation problem with varying requests and with resources of limited capacity shared by multiple requests. It is modeled as a set of heterogeneous restless multiarmed bandit problems (RMABPs) connected by constraints imposed by resource capacity. Following Whittle's relaxation idea and Weber and Weiss' asymptotic optimality proof, we propose a simple policy and prove it to be asymptotically optimal in a regime where both arrival rates and capacities increase. We provide a simple sufficient condition for asymptotic optimality of the policy and, in complete generality, propose a method that generates a set of candidate policies for which asymptotic optimality can be check..